김희진

[260617]-최대공약수와 최소공배수

4 min read

코딩테스트 연습 - 최대공약수와 최소공배수 | 프로그래머스 스쿨

[ 템플릿 코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(int n, int m) {
    vector<int> answer;
    return answer;
}

[ 풀이 ]

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(int n, int m)
{
    vector<int> answer;
 
    int gcd = 1;
 
    for (int i = 1; i <= min(n, m); i++)
    {
        if (n % i == 0 && m % i == 0)
        {
            gcd = i;
        }
    }
 
    int lcm = n * m / gcd;
 
    answer.push_back(gcd);
    answer.push_back(lcm);
 
    return answer;
}

[ 해설 ]

#include <string>      // string 자료형을 사용하기 위한 헤더
#include <vector>      // vector 컨테이너를 사용하기 위한 헤더
 
using namespace std;   // std:: 를 생략하고 사용하기 위해 선언
 
// 최대공약수와 최소공배수를 반환하는 함수
vector<int> solution(int n, int m)
{
    vector<int> answer;    // 결과를 저장할 벡터
                            // answer[0] = 최대공약수
                            // answer[1] = 최소공배수
 
    int gcd = 1;           // 최대공약수를 저장할 변수
                           // 최소값은 1이므로 초기값을 1로 설정
 
    // 최대공약수 찾기
    // 1부터 n과 m 중 더 작은 수까지 반복
    // 두 수의 공약수 중 가장 큰 값을 찾는다.
    for (int i = 1; i <= min(n, m); i++)
    {
        // i가 n과 m을 모두 나누어 떨어지게 하면
        // i는 두 수의 공약수이다.
        if (n % i == 0 && m % i == 0)
        {
            // 반복문이 작은 수부터 큰 수 순서로 진행되므로
            // 조건을 만족할 때마다 gcd를 갱신하면
            // 마지막에 저장되는 값이 가장 큰 공약수(최대공약수)가 된다.
            gcd = i;
        }
    }
 
    // 최소공배수 계산
    // 두 수의 곱을 최대공약수로 나누면 최소공배수가 된다.
    int lcm = n * m / gcd;
 
    // 계산한 최대공약수를 결과 벡터에 저장
    answer.push_back(gcd);
 
    // 계산한 최소공배수를 결과 벡터에 저장
    answer.push_back(lcm);
 
    // [최대공약수, 최소공배수] 형태의 벡터 반환
    return answer;
}
  • 최대공약수(GCD): 유클리드 호제법 사용
  • 최소공배수(LCM):

[ 타 답안 ]

#include <string>      // string 자료형을 사용하기 위한 헤더
#include <vector>      // vector 컨테이너를 사용하기 위한 헤더
 
using namespace std;   // std::를 생략하기 위해 사용
 
// 최대공약수(GCD)를 구하는 함수
// 유클리드 호제법 사용
int GCD(int a, int b)
{
    // b가 0이 될 때까지 반복
    while (b != 0)
    {
        // 현재 b 값을 임시 저장
        int temp = b;
 
        // a를 b로 나눈 나머지를 b에 저장
        // 다음 반복에서 계산에 사용됨
        b = a % b;
 
        // 기존 b 값을 a에 저장
        a = temp;
    }
 
    // 반복문이 종료되면
    // a에는 최대공약수가 저장되어 있음
    return a;
}
 
// 최대공약수와 최소공배수를 구하는 함수
vector<int> solution(int n, int m)
{
    // GCD 함수를 호출하여 최대공약수 계산
    int gcd = GCD(n, m);
 
    // 최소공배수 계산
    // (두 수의 곱) ÷ (최대공약수)
    int lcm = n * m / gcd;
 
    // {최대공약수, 최소공배수} 형태의 벡터 반환
    return {gcd, lcm};
}

C++ CodingTest

Graph View